This invention concerns the operation of digital computers, and is particularly directed to the processing of branching instructions in a digital computer employing pipelined instruction processing.
Branch instructions can reduce the speed and efficiency of pipelined instruction processing. This deleterious effect has an even greater impact on the performance of processors with multiple pipelines processing a single instruction stream. Such processors include those referred to as "scalable compound instruction-set machines" (SCISM). A machine with SCISM architecture is taught in detail in the cross-referenced patent applications.
Branch prediction schemes have been proposed to reduce the performance penalty extracted by branch instruction execution. Two such schemes are of interest. The first involves dynamic prediction of branch outcomes by tagging branch instructions in an instruction cache with predictive information regarding their outcomes. See, for example, the article by J.E. Smith entitled "A Study of Branch Prediction Strategies", in the March 1981 PROCEEDINGS of the Eighth Annual Symposium on Computer Architecture. SCISM architecture which provides spare information capacity in an instruction stream is particularly adapted for this scheme. In this regard, a bit, called a "compounding" or "C"-bit, is provided in every half word of a SCISM instruction stream. Whenever one of these bits follows an instruction which can be executed in parallel with ("compounded with") the following instruction, the C-bit in the first halfword of the first instruction is set to indicate this capability. If the instruction is longer than one-half word, the compounding provides unused bits for the extra halfwords. The C-bit or bits which are not used in the compounding scheme are available for alternate uses. For branch instructions, one such use is the prediction of the outcome of a branch instruction.
A second branch prediction strategy involves the use of a branch target buffer (BTB) which contains a history of the outcome of executed branch instructions. When a branch instruction is first executed, its outcome is stored in the BTB. When the branch instruction is executed a second time, its predicted outcome is the outcome stored in the BTB. Such a mechanism is described in detail in the article by J.K.F. LEE ET AL, entitled "Branch Prediction Strategies in Branch Target Buffer Design" in the January 1984 issue of IEEE COMPUTER.
While both dynamic prediction and branch target buffer mechanisms do speed up a pipeline which executes an instruction stream including branch instructions, the techniques involved have not been adapted for application in a SCISM architecture. Further, the advantages of parallelism enjoyed in multiple-pipeline architectures have not yet been realized in processing branch instructions.